﻿// homework4_problem1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include<iostream>
#include<string>
using namespace std; /*本程序是使用Dijkstra算法来求解最短路径的问题采用的邻接矩阵来存储图*/ 
					 //记录起点到每个顶点的最短路径的信息
struct Dis {	
	string path;	
	int value;	
	bool visit;	
	Dis() {		
		visit = false;		
		value = 0;		
		path = "";	
	}
}; 
class Graph_DG {
private:	
	int vexnum;//图的顶点个数	
	int edge;//图的边数	
	int **arc;//邻接矩阵	
	Dis *dis;//记录各个顶点最短路径的信息
public:	//构造函数	
	Graph_DG(int vexnum, int edge);	//析构函数	
	~Graph_DG();	//判断我们每次输入的边的信息是否合法	
					//顶点从1开始编号	
	bool check_edge_value(int start, int end, int weight);	//创建图	
	void createGraph();	//打印邻接矩阵	
	void print();	//求最短路径	
	void Dijkstra(int begin);	//打印最短路径	
	void print_path(int); 
};
Graph_DG::Graph_DG(int vexnum, int edge) {	//初始化顶点数和边数	
	this->vexnum = vexnum;	
	this->edge = edge;	//为邻接矩阵开辟空间和赋初值	
	arc = new int*[this->vexnum];	
	dis = new Dis[this->vexnum];	
	for (int i = 0; i < this->vexnum; i++)	{		
		arc[i] = new int[this->vexnum];		
		for (int k = 0; k < this->vexnum; k++)	{			//邻接矩阵初始化为无穷大
			arc[i][k] = INT_MAX;		
		}	
	}
} 
//析构函数
Graph_DG::~Graph_DG(){	
	delete[] dis;	
	for (int i = 0; i < this->vexnum; i++)	{		
		delete this->arc[i];	
	}	
	delete arc;
} 
//判断我们每次输入的边的信息是否合法
//顶点从0开始编号
bool Graph_DG::check_edge_value(int start, int end, int weight){	//修改完毕
	if (start<0 || end<0 || start>vexnum-1 || end>vexnum-1 || weight < 0) 	{		
		return false;	
	}	
	return true;
} 
void Graph_DG::createGraph(){		//修改完毕
	//cout << "请输入每条边的起点和终点（顶点编号从0开始）以及其权重" << endl;	
	int start;	
	int end;	
	int weight;	
	int count = 0;	
	while (count != this->edge)	{		//计数，直到输入了等于边数行的数据
		cin >> start >> end >> weight;		//传入起点、重点、权重
		//首先判断边的信息是否合法		
		while (!this->check_edge_value(start, end, weight)) {			
			//cout << "输入的边的信息不合法，请重新输入" << endl;			
			cin >> start >> end >> weight;		
		}		
		//对邻接矩阵对应上的点赋值		
		arc[start][end] = weight;		//从0开始编号即可直接赋值，不需要调整坐标
		//无向图添加上这行代码		
		//arc[end][start] = weight;		
		++count;	
	}
} 
void Graph_DG::Dijkstra(int begin) {	//首先初始化我们的dis数组，传入参数为起点	
	int i;	
	for (i = 0; i < this->vexnum; i++) {		//设置当前的路径		
		dis[i].path = to_string(begin) + "-" + to_string(i);		
		dis[i].value = arc[begin][i];	
	}	
	//设置起点的到起点的路径为0	
	dis[begin].value = 0;	
	dis[begin].visit = true; 	
	int count = 1;	//计算剩余的顶点的最短路径（剩余this->vexnum-1个顶点）	
	while (count != this->vexnum) {		//temp用于保存当前dis数组中最小的那个下标		
										//min记录的当前的最小值		
		int temp = 0;		
		int min = INT_MAX;		
		for (i = 0; i < this->vexnum; i++) {			
			if (!dis[i].visit && dis[i].value<min) {				
				min = dis[i].value;				
				temp = i;			
			}		
		}		
		//cout << temp + 1 << "  "<<min << endl;		
		//把temp对应的顶点加入到已经找到的最短路径的集合中		
		dis[temp].visit = true;		
		++count;		
		for (i = 0; i < this->vexnum; i++) {			
			//注意这里的条件arc[temp][i]!=INT_MAX必须加，不然会出现溢出，从而造成程序异常			
			if (!dis[i].visit && arc[temp][i] != INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) {				//如果新得到的边可以影响其他为访问的顶点，那就就更新它的最短路径和长度				
				dis[i].value = dis[temp].value + arc[temp][i];
				dis[i].path = dis[temp].path + "-" + to_string(i);			
			}		
		}	
	} 
} 
void Graph_DG::print_path(int begin) {	
	string str;	str = "D" + to_string(begin);	
	//cout << "以" << str << "为起点的图的最短路径为：" << endl;	
	for (int i = 1; i != this->vexnum; i++) {		
		if (dis[i].value != INT_MAX)			
			cout << "0-" << i << " " << dis[i].value << " " << dis[i].path << endl;		
		else {			
			cout << "0-" << i << " " << "999 -" << endl;
		}	
	}
}
bool check(int Vexnum, int edge) { 
	if (Vexnum <= 0 || edge <= 0 || ((Vexnum * (Vexnum - 1)) / 2) < edge)		
		return false;	
	return true; 
}
int main() { 
	int vexnum; 
	int edge; 	
	//cout << "输入图的顶点个数和边的条数：" << endl;	
	cin >> vexnum >> edge;	
	while (!check(vexnum, edge)) { 
		cout << "输入的数值不合法，请重新输入" << endl;		
		cin >> vexnum >> edge; 
	}	
	Graph_DG graph(vexnum, edge);	
	graph.createGraph();		
	graph.Dijkstra(0);	
	graph.print_path(0);	
	system("pause");	
	return 0;
}



// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
